---
id: 5a23c84252665b21eecc8010
title: 'Алгоритми сортування: сортування Шелла'
challengeType: 1
forumTopicId: 302317
dashedName: sorting-algorithmsshell-sort
---

# --description--

Напишіть функцію для сортування масиву елементів за допомогою алгоритму сортування Шелла, що є сортуванням зі зменшенням приросту. Функція має повернути відсортований масив.

Сортування Шелла (також відоме як метод Шелла) названо на честь його автора — Дональда Шелла, який опублікував алгоритм у 1959 році.

Сортування Шелла — це послідовність перемежованих сортувань включенням на основі послідовності приросту. Величина приросту зменшується після кожного проходження, поки не дорівнюватиме 1.

Сортування з величиною приросту 1 — це базове сортування включенням, але до цього часу дані практично відсортовані, що є «найкращим випадком» для сортування включенням.

Будь-яка послідовність сортуватиме дані, поки вона закінчується на 1, але деякі працюють краще за інші.

Емпіричні дослідження показали, що геометрична послідовність приросту з відношенням приблизно 2.2 добре працює на практиці.

# --hints--

`shellSort` має бути функцією.

```js
assert(typeof shellSort == 'function');
```

`shellSort([25, 32, 12, 7, 20])` має повернути масив.

```js
assert(Array.isArray(shellSort([25, 32, 12, 7, 20])));
```

`shellSort([25, 32, 12, 7, 20])` має повернути `[7, 12, 20, 25, 32]`.

```js
assert.deepEqual(shellSort([25, 32, 12, 7, 20]), [7, 12, 20, 25, 32]);
```

`shellSort([38, 45, 35, 8, 13])` має повернути `[8, 13, 35, 38, 45]`.

```js
assert.deepEqual(shellSort([38, 45, 35, 8, 13]), [8, 13, 35, 38, 45]);
```

`shellSort([43, 36, 20, 34, 24])` має повернути `[20, 24, 34, 36, 43]`.

```js
assert.deepEqual(shellSort([43, 36, 20, 34, 24]), [20, 24, 34, 36, 43]);
```

`shellSort([12, 33, 26, 18, 1, 16, 38])` має повернути `[1, 12, 16, 18, 26, 33, 38]`.

```js
assert.deepEqual(shellSort([12, 33, 26, 18, 1, 16, 38]), [
  1,
  12,
  16,
  18,
  26,
  33,
  38
]);
```

`shellSort([3, 39, 48, 16, 1, 4, 29])` має повернути `[1, 3, 4, 16, 29, 39, 48]`.

```js
assert.deepEqual(shellSort([3, 39, 48, 16, 1, 4, 29]), [
  1,
  3,
  4,
  16,
  29,
  39,
  48
]);
```

# --seed--

## --seed-contents--

```js
function shellSort(a) {

}
```

# --solutions--

```js
function shellSort(a) {
  for (var h = a.length; h > 0; h = parseInt(h / 2)) {
    for (var i = h; i < a.length; i++) {
      var k = a[i];
      for (var j = i; j >= h && k < a[j - h]; j -= h) a[j] = a[j - h];
      a[j] = k;
    }
  }
  return a;
}
```
